Part 48: The Wardialer

Part 48 - The Wardialer


=== Trash World Inbox ===

A slightly different solution than I had but the general approach is similar. That's not too surprising - the single EXA constraint limits the options. Also, I'm not sure if I've used the REP variable label trick before. I know I considered it for other puzzles but often it didn't make much of a difference.


=== The Wardialer ===



It is time to create that wardialer we heard about in the chat.


OST: Network Exploration

The assignment:
- File 300 contains a phone number where one to three of the digits have been replaced with a placeholder (X). Using your modem, dial all possible phone numbers that could be generated by replacing the placeholders with the digits 0 through 9. When you discover a valid phone number that connects to another host, append it to file 301.
- Note that the phone numbers must be dialed and appended in a specific order such that a placeholder is only incremented when the placeholder to the right cycles through all possible values from 0 to 9 and is reset to 0.
- For more information see "Hacker Skills: Model Control at the Direct Level" in the second issue of the zine.

Another modem level. The second point of the assignment is just a complicated way to say the results should be ordered from low to high.

The files in the remote hosts contain some other phone numbers. They don't match the partial number in file 300 so I have no use for them. There's also some hardware registers out there I don't care about for this assignment.

For this first test, the partial number is 94-0-177X-X96X. To get the phone numbers in order, I should first dial 94-0-1770-0960, then 94-0-1770-0961 and so on.
The easiest way to handle this is if I can just update those placeholders in-place. However, I need to keep track which values are placeholders.

I'm thinking I can do this by choosing alternate numbers that are outside the normal range and that can easily be converted back to the actual ones.
I think I'll just subtract 10 from every number, so the digit 0 becomes -10, and the digit 9 becomes -1. To dial it, I'll just have to add 10 again.
This replaces all the X's (non-digits) with -10, which will dial the digit 0. Let's just try dialing the first number.
While I was writing this part I suddenly realized my choice to offset everything by 10 is even more useful than I thought. I can use the modulo function to change them into the correct digit and send them to the #DIAL at the same time.

As a side note, it turns out that there's no single definition for modulo operations on negative numbers. Is -4 / 10 equal to -1 remainder 6 or to 0 remainder -4? Different programming languages disagree on this so this code might fail if run on anything else than an EXA. In this case, MODI -4 10 is equal to 6, which is what I need.

Now, what's next? Creating a REPL to go check if there's a connection? Sure, we could do that, but it's always good to pay close attention to what's happening in the system.

In this case, I'm coding for the NETronics NET40 modem, not the TEC EXA-Blaster from the previous assignments. It's almost identical but it has one significant difference.



There's a number visible on this #DIAL register. That means it isn't write-only. When you read it, it returns 1 when the modem is connected, 0 otherwise. That means the entire connection check is just a single TEST of the #DIAL register.
So the test code is just this. I'll implement storing the number later. Let's first focus on updating the number in the right order. Currently it ignores whether the number is correct and just continues on, so I can test that part independently.

Because the EXA just finished dialing, the cursor is already at EOF. I want to update the numbers right to left, so that's convenient. All file access moves the cursor. ADDI F 1 F would add 1 to the value in F and write that to the NEXT position in F. So I need an intermediate register.

In most cases, it will just add 1 to the value and write that back to the file. The jump to ROLLOVER only happens if T is 0 - that is, if I just tried all 10 digits. In that case, I need to write -10 back to that value so the code keeps recognizing it as a placeholder. Then I skip over it, and find the next placeholder in the file.

Next round, the first placeholder is -10 again, it becomes -9, and so on, until it rolls back round to 0, the ROLLOVER is triggered and the next digit is incremented. It works recursively for however many placeholders there are.

Once all numbers have been tried, it will rollover past the final placeholder in the file, and get in an infinite loop as it keeps SEEKing to the start forever.

Let's handle that.

There's no direct way to test if the cursor is at the start of the file. You could test if the digit at the current location is the same as the one at the start but of course digits can occur multiple times. Since the phone numbers are always 11 digits I decided to use a simple counter.

Just after dialing, 11 is stored to X. The NEXTNUMBER loop is amended:
A SUBI and a TEST. At the bottom of the code, MARK END just has a WIPE after it to get rid of the temporary file.

With that done, it's time to copy the valid numbers.

I can replace the TODO from earlier with a simple snippet that copies the actual digits over M:

Then, the final touch is an XB that can receive the data.




Fuck nazis. Anyway, XB can just read M 88 times, because for every test there are 8 valid numbers, so that's 8 times 11 digits.

This is my first working solution.



With 147 lines, the fully unrolled XB just barely fits. And with 65K cycles, it takes an age and a half to even verify that this is a working solution.

So, I'm at 65154/147/1. Top percentiles are 20.7K, 47 and 1. Let's see if I can improve some things.


First of all, for a quick reduction of the size, I'll just roll up loops.
Simply replacing all three @REPs with a COPY number T followed by a loop that has a SUBI T 1 T and a TJMP reduces the size to 52, but the cycle count becomes 88338.

If XB KILLs XA after it got all the phone numbers, I can remove XA's counter and completion check in NEXTNUMBER. This brings the size down to 51.
67922/51/3. It doesn't just save a line, it's also quite a bit faster.

I also have a couple non-conditional JUMP statements. Perhaps I can get rid of one by reordering the code.
66950/50/3. The JUMP from NEXTNUMBER to DIAL has been removed. After a successful connection, the code now falls through into the ROLLOVER but that just adds an unused -10 to the EOF, it does no harm.

And for the final size reduction, I can save a line by replacing the COPY #DIAL T with MULI #DIAL 11 T. The FJMP will still act the same, but the COPY 11 T just below that is no longer necessary. 66942/49/3. Only 2 lines away from the top percentile score.


Except for rolling up the loops, all the changes I just did not only reduced the size, but also made the solution run faster.

Keeping the speed improvements and unrolling all three loops again, I'm at 43904/145/3. Much better than what I had but still far from the top percentile.


I have a couple ideas on how to get there. For instance, it would be much faster to update the placeholders from left to right, but that would require sorting in XB. Or, you could send multiple digits over M with one message, because 4 digits fit in a number. But that would require multiplying the digits by factors of 10, and that's difficult when I also need the MODI trick to deal with the placeholders. It might not really be faster.

The third option and the one which I think is most likely to work, is parallelism. You could have one EXA dialing while another is updating the number. Of course you can't do that on the same number so you'd have to make a copy. Perhaps one EXA could try all numbers where the last placeholder is odd, another where all of them are even.

And the final option, of course, is to cheese it by building special cases for the slowest tests.

I don't like to cheese the tests if I don't have to, so let's start with the third option. Here is the entire code:

The 'main' XA works the same as before, replacing placeholders with -10. After that it sends the whole file over M. The ODD EXA retrieves the whole file, then changes the very last placeholder to -9 (corresponding to the digit 1 for dialing).

The communications in LOCAL mode are purely to prevent both EXAs from dialing at the same time. As soon as one is done dialing, it releases the other with an M message so it can start dialing the next number. I added MODE instructions around the copy-to-XB code so that part is done in GLOBAL mode.

I also needed some special code in the NEXTNUMBER. It keeps X set to zero unless a rollover is triggered, in which case X becomes 1. The code updates each placeholder value by adding (2 - X). That way, it tries every 2nd number for the last placeholder, but every single number for the others.

In the old logic, once the value was increased all the way up to 0 this triggered the ROLLOVER through an FJMP. For the odd EXA, this won't work because the value will jump from -1 to 1, both considered true. I added special handling for this case through the ODDROLLOVER.

XB is mostly the same. I had to partially roll up the loop to make space for the extra code, and of course kill the additional EXA and its file.

38579/127/4. An improvement but not as much as I'd hoped. It might be slightly faster to release the other XA before sending data over GLOBAL M, but that leads to an issue where the odd EXA gets stuck once the even one tries all numbers and gets in the infinite loop, never reaching the VOID M.

There are specific tests that run very slowly. It's because all the placeholders are near the start of the phone number, and every time it seeks through the entire file from end to start.

I can partially solve this by storing the location of the last placeholder in the file, like so:

This FIND loop runs after the placeholders have been replaced by -10, but before the data is copied to the ODD EXA. The additional value is copied to the ODD EXA too. I need an extra SEEK -1 before the MAKELASTODD in case the value found is exactly -10. Then, just after the RELEASE, when a number was dialed, the cursor is sitting on this additional value in the file, and a SEEK F brings it directly to the last placeholder. The SEEK F moves the cursor one place forward before seeking back, but this works out because the NEXTNUMBER starts with a SEEK -1 anyway.

22549/139/4. Getting much closer to the top percentile. The slowest test is now one that has the last placeholder near the end of the file, but two others near the start.

That could possibly be solved by keeping track of the location of multiple placeholders, but that's a lot more difficult than what I just did. Some tests only have one placeholder at all, so you'd have to handle that. It'd also require some additional place to even store it, where it could be accessed quickly. And I'm running out of space for lines of code. So, I'll leave further improvements to you. The full code is just below in the appendix if you want to give it a go.

Next time, we help selenium_wolf.


=== Appendix ===

Wardialer 22549/139/4